| 翻訳と辞書 |
| FKT algorithm ： ウィキペディア英語版 |
FKT algorithm
The FKT algorithm, named after Fisher, Kasteleyn, and Temperley, counts the number of perfect matchings in a planar graph in polynomial time. This same task is #P-complete for general graphs. Counting the number of matchings, even for planar graphs, is also #P-complete. The key idea is to convert the problem into a Pfaffian computation of a skew-symmetric matrix derived from a planar embedding of the graph. The Pfaffian of this matrix is then computed efficiently using standard determinant algorithms.
==History==
The problem of counting planar perfect matchings has its roots in statistical mechanics and chemistry, where the original question was: If diatomic molecules are adsorbed on a surface, forming a single layer, how many ways can they be arranged? The partition function is an important quantity that encodes the statistical properties of a system at equilibrium and can be used to answer the previous question. However, trying to compute the partition function from its definition is not practical. Thus to exactly solve a physical system is to find an alternate form of the partition function for that particular physical system that is sufficiently simple to calculate exactly. In the early 1960s, the definition of ''exactly solvable'' was not rigorous. Computer science provided a rigorous definition with the introduction of polynomial time, which dates to 1965. Similarly, the notation of not ''exactly solvable'' should correspond to #P-hardness, which was defined in 1979.
Another type of physical system to consider is composed of dimers, which is a polymer with two atoms. The dimer model counts the number of dimer coverings of a graph. Another physical system to consider is the bonding of H2O molecules in the form of ice. This can be modelled as a directed, 3-regular graph where the orientation of the edges at each vertex cannot all be the same. How many edge orientations does this model have?
Motivated by physical systems involving dimers, in 1961, Kasteleyn and Temperley and Fisher independently found the number of domino tilings for the ''m''-by-''n'' rectangle. This is equivalent to counting the number of perfect matchings for the ''m''-by-''n'' lattice graph. By 1967, Kasteleyn had generalized this result to all planar graphs.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「FKT algorithm」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|